Luogu P1047 校门外的树

Posted on | In |
Words count in article: 591 | Reading time ≈ 3

首先，如题目算法标签所言，线段树（其实也是杂技写法）

不多赘述，建树、修改、查询一气呵成，就算是杂技，也要做杂技中的豪杰（逃）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define N 2000010
using namespace std;
struct node
{
    int left,right;
    long long val,sum;
};struct node a[4*N];
int data[N],n,m,x,y,b;
long long z;
void pushup(int p)
{
    a[p].sum=a[2*p].sum+a[2*p+1].sum;
}
void pushdown(int p)
{
    if(a[p].val!=-1)
    {
        a[2*p].val=a[p].val;
        a[2*p+1].val=a[p].val;
        a[2*p].sum=(a[2*p].right-a[2*p].left+1)*a[p].val;
        a[2*p+1].sum=(a[2*p+1].right-a[2*p+1].left+1)*a[p].val;
        a[p].val=-1;
    }
}//pushup、pushdown是基本操作，不多讲
void build(int p,int l,int r)
{
    a[p].left=l;
    a[p].right=r;
    a[p].val=-1;
    if(l==r)
    {
        a[p].sum=data[l];
        return;
    }
    int mid=(a[p].left+a[p].right)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    a[p].sum=a[2*p].sum+a[2*p+1].sum;
}//建树也很简单
long long query(int p,int l,int r)
{
    if(a[p].left==l&&a[p].right==r)
        return a[p].sum;
    pushdown(p);
    int mid=(a[p].left+a[p].right)/2;
    if(r<=mid)
        return query(2*p,l,r);
    else if(l>mid)
        return query(2*p+1,l,r);
    else
        return query(2*p,l,mid)+query(2*p+1,mid+1,r);
}//查询
void change(int p,int l,int r,long long d)
{
    if(a[p].left==l&&a[p].right==r)
    {
        a[p].sum=(l-r+1)*d;
        a[p].val=0;
        return;
    }
    pushdown(p);
    int mid=(a[p].left+a[p].right)/2;
    if(r<=mid)
        change(2*p,l,r,d);
    else if(l>mid)
        change(2*p+1,l,r,d);
    else
    {
        change(2*p,l,mid,d);
        change(2*p+1,mid+1,r,d);
    }
    pushup(p);
}//此函数是与模板唯一的差别，将砍掉的树的值赋为0，这样就只需查询根节点处的区间和了
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n+1;i++)
        data[i]=1;//将每个位置的初值赋为1，方便查询时只查根节点。值得注意的是，由于这里是算了0这个位置的，所以n、x、y都要相应的加1
    build(1,1,n+1);
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        change(1,x+1,y+1,0);
    }
    cout<<query(1,1,n+1);
    return 0;
}

比较简单不多说，具体注释看代码

0%